Fragmenty [A]

Limit pamięci: 64 MB

Dany jest pewien zbiór liczb całkowitych dodatnich . Jeżeli jest ciągiem cyfr, to możemy zapytać, ile razy występuje on, jako fragment (czyli spójny kawałek), w liczbach ze zbioru . Ciąg może występować jako fragment jednej liczby wielokrotnie - chcemy wówczas uwzględnić wszystkie jego wystąpienia.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz (, ) oznaczające liczbę wierszy opisu zbioru oraz liczbę ciągów cyfr stanowiących zapytania. Każdy z kolejnych wierszy zawiera dwie liczby całkowite oraz . Liczby te spełniają następujące nierówności: i reprezentują następujący zbiór:

Każdy z kolejnych wierszy zawiera jeden ciąg cyfr , złożony z co najmniej jednej i co najwyżej dziewiętnastu cyfr .

Wyjście

Twój program powinien wypisać na standardowe wyjście wierszy, z których -ty powinien zawierać jedną liczbę całkowitą: łączną liczbę wystąpień we wszystkich liczbach ze zbioru , z uwzględnieniem wielokrotnych wystąpień w poszczególnych liczbach z .

Przykład

Dla danych wejściowych:

1 3
2220 2223
222
0
07

poprawną odpowiedzią jest:

5
1
0

Autor zadania: Jakub Radoszewski.